/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements. See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership. The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the  "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
/*
 * $Id$
 */
package wx.xml.xalan.xalan.transformer;

import java.text.CollationKey;
import java.util.Vector;

import javax.xml.transform.TransformerException;

import wx.xml.xalan.xml.dtm.DTM;
import wx.xml.xalan.xml.dtm.DTMIterator;
import wx.xml.xalan.xpath.XPathContext;
import wx.xml.xalan.xpath.objects.XNodeSet;
import wx.xml.xalan.xpath.objects.XObject;

/**
 * This class can sort vectors of DOM nodes according to a select pattern.
 *
 * @xsl.usage internal
 */
public class NodeSorter {

    /**
     * Current XPath context
     */
    XPathContext m_execContext;

    /**
     * Vector of NodeSortKeys
     */
    Vector m_keys;  // vector of NodeSortKeys

//  /**
//   * TODO: Adjust this for locale.
//   */
//  NumberFormat m_formatter = NumberFormat.getNumberInstance();

    /**
     * Construct a NodeSorter, passing in the XSL TransformerFactory
     * so it can know how to get the node data according to
     * the proper whitespace rules.
     *
     * @param p Xpath context to use
     */
    public NodeSorter(XPathContext p) {
        m_execContext = p;
    }

    /**
     * Given a vector of nodes, sort each node according to
     * the criteria in the keys.
     *
     * @param v       an vector of Nodes.
     * @param keys    a vector of NodeSortKeys.
     * @param support XPath context to use
     * @throws javax.xml.transform.TransformerException
     */
    public void sort(DTMIterator v, Vector keys, XPathContext support)
        throws javax.xml.transform.TransformerException {

        m_keys = keys;

        // QuickSort2(v, 0, v.size() - 1 );
        int n = v.getLength();

        // %OPT% Change mergesort to just take a DTMIterator?
        // We would also have to adapt DTMIterator to have the function
        // of NodeCompareElem.

        // Create a vector of node compare elements
        // based on the input vector of nodes
        Vector nodes = new Vector();

        for (int i = 0; i < n; i++) {
            NodeCompareElem elem = new NodeCompareElem(v.item(i));

            nodes.addElement(elem);
        }

        Vector scratchVector = new Vector();

        mergesort(nodes, scratchVector, 0, n - 1, support);

        // return sorted vector of nodes
        for (int i = 0; i < n; i++) {
            v.setItem(((NodeCompareElem) nodes.elementAt(i)).m_node, i);
        }
        v.setCurrentPos(0);

        // old code...
        //NodeVector scratchVector = new NodeVector(n);
        //mergesort(v, scratchVector, 0, n - 1, support);
    }

    /**
     * Return the results of a compare of two nodes.
     * TODO: Optimize compare -- cache the getStringExpr results, key by m_selectPat + hash of node.
     *
     * @param n1      First node to use in compare
     * @param n2      Second node to use in compare
     * @param kIndex  Index of NodeSortKey to use for sort
     * @param support XPath context to use
     * @return The results of the compare of the two nodes.
     * @throws TransformerException
     */
    int compare(
        NodeCompareElem n1, NodeCompareElem n2, int kIndex, XPathContext support)
        throws TransformerException {

        int         result = 0;
        NodeSortKey k      = (NodeSortKey) m_keys.elementAt(kIndex);

        if (k.m_treatAsNumbers) {
            double n1Num, n2Num;

            if (kIndex == 0) {
                n1Num = ((Double) n1.m_key1Value).doubleValue();
                n2Num = ((Double) n2.m_key1Value).doubleValue();
            } else if (kIndex == 1) {
                n1Num = ((Double) n1.m_key2Value).doubleValue();
                n2Num = ((Double) n2.m_key2Value).doubleValue();
            }

      /* Leave this in case we decide to use an array later
      if (kIndex < maxkey)
      {
      double n1Num = (double)n1.m_keyValue[kIndex];
      double n2Num = (double)n2.m_keyValue[kIndex];
      }*/
            else {

                // Get values dynamically
                XObject r1 = k.m_selectPat.execute(m_execContext, n1.m_node,
                    k.m_namespaceContext);
                XObject r2 = k.m_selectPat.execute(m_execContext, n2.m_node,
                    k.m_namespaceContext);
                n1Num = r1.num();

                // Can't use NaN for compare. They are never equal. Use zero instead.
                // That way we can keep elements in document order.
                //n1Num = Double.isNaN(d) ? 0.0 : d;
                n2Num = r2.num();
                //n2Num = Double.isNaN(d) ? 0.0 : d;
            }

            if ((n1Num == n2Num) && ((kIndex + 1) < m_keys.size())) {
                result = compare(n1, n2, kIndex + 1, support);
            } else {
                double diff;
                if (Double.isNaN(n1Num)) {
                    if (Double.isNaN(n2Num))
                        diff = 0.0;
                    else
                        diff = -1;
                } else if (Double.isNaN(n2Num))
                    diff = 1;
                else
                    diff = n1Num - n2Num;

                // process order parameter
                result = (int) ((diff < 0.0)
                                ? (k.m_descending ? 1 : -1)
                                : (diff > 0.0) ? (k.m_descending ? -1 : 1) : 0);
            }
        }  // end treat as numbers
        else {
            CollationKey n1String, n2String;

            if (kIndex == 0) {
                n1String = (CollationKey) n1.m_key1Value;
                n2String = (CollationKey) n2.m_key1Value;
            } else if (kIndex == 1) {
                n1String = (CollationKey) n1.m_key2Value;
                n2String = (CollationKey) n2.m_key2Value;
            }

      /* Leave this in case we decide to use an array later
      if (kIndex < maxkey)
      {
        String n1String = (String)n1.m_keyValue[kIndex];
        String n2String = (String)n2.m_keyValue[kIndex];
      }*/
            else {

                // Get values dynamically
                XObject r1 = k.m_selectPat.execute(m_execContext, n1.m_node,
                    k.m_namespaceContext);
                XObject r2 = k.m_selectPat.execute(m_execContext, n2.m_node,
                    k.m_namespaceContext);

                n1String = k.m_col.getCollationKey(r1.str());
                n2String = k.m_col.getCollationKey(r2.str());
            }

            // Use collation keys for faster compare, but note that whitespaces
            // etc... are treated differently from if we were comparing Strings.
            result = n1String.compareTo(n2String);

            //Process caseOrder parameter
            if (k.m_caseOrderUpper) {
                String tempN1 = n1String.getSourceString().toLowerCase();
                String tempN2 = n2String.getSourceString().toLowerCase();

                if (tempN1.equals(tempN2)) {

                    //java defaults to upper case is greater.
                    result = result == 0 ? 0 : -result;
                }
            }

            //Process order parameter
            if (k.m_descending) {
                result = -result;
            }
        }  //end else

        if (0 == result) {
            if ((kIndex + 1) < m_keys.size()) {
                result = compare(n1, n2, kIndex + 1, support);
            }
        }

        if (0 == result) {

            // I shouldn't have to do this except that there seems to
            // be a glitch in the mergesort
            // if(r1.getType() == r1.CLASS_NODESET)
            // {
            DTM dtm = support.getDTM(n1.m_node); // %OPT%
            result = dtm.isNodeAfter(n1.m_node, n2.m_node) ? -1 : 1;

            // }
        }

        return result;
    }

    /**
     * This implements a standard Mergesort, as described in
     * Robert Sedgewick's Algorithms book.  This is a better
     * sort for our purpose than the Quicksort because it
     * maintains the original document order of the input if
     * the order isn't changed by the sort.
     *
     * @param a       First vector of nodes to compare
     * @param b       Second vector of  nodes to compare
     * @param l       Left boundary of  partition
     * @param r       Right boundary of  partition
     * @param support XPath context to use
     * @throws TransformerException
     */
    void mergesort(Vector a, Vector b, int l, int r, XPathContext support)
        throws TransformerException {

        if ((r - l) > 0) {
            int m = (r + l) / 2;

            mergesort(a, b, l, m, support);
            mergesort(a, b, m + 1, r, support);

            int i, j, k;

            for (i = m; i >= l; i--) {

                // b[i] = a[i];
                // Use insert if we need to increment vector size.
                if (i >= b.size())
                    b.insertElementAt(a.elementAt(i), i);
                else
                    b.setElementAt(a.elementAt(i), i);
            }

            i = l;

            for (j = (m + 1); j <= r; j++) {

                // b[r+m+1-j] = a[j];
                if (r + m + 1 - j >= b.size())
                    b.insertElementAt(a.elementAt(j), r + m + 1 - j);
                else
                    b.setElementAt(a.elementAt(j), r + m + 1 - j);
            }

            j = r;

            int compVal;

            for (k = l; k <= r; k++) {

                // if(b[i] < b[j])
                if (i == j)
                    compVal = -1;
                else
                    compVal = compare((NodeCompareElem) b.elementAt(i),
                        (NodeCompareElem) b.elementAt(j), 0, support);

                if (compVal < 0) {

                    // a[k]=b[i];
                    a.setElementAt(b.elementAt(i), k);

                    i++;
                } else if (compVal > 0) {

                    // a[k]=b[j];
                    a.setElementAt(b.elementAt(j), k);

                    j--;
                }
            }
        }
    }

    /**
     * This is a generic version of C.A.R Hoare's Quick Sort
     * algorithm.  This will handle arrays that are already
     * sorted, and arrays with duplicate keys.<BR>
     *
     * If you think of a one dimensional array as going from
     * the lowest index on the left to the highest index on the right
     * then the parameters to this function are lowest index or
     * left and highest index or right.  The first time you call
     * this function it will be with the parameters 0, a.length - 1.
     *
     * @param v       a vector of integers
     * @param lo0     left boundary of array partition
     * @param hi0     right boundary of array partition
     *
     */

  /*  private void QuickSort2(Vector v, int lo0, int hi0, XPathContext support)
      throws javax.xml.transform.TransformerException,
             java.net.MalformedURLException,
             java.io.FileNotFoundException,
             java.io.IOException
    {
      int lo = lo0;
      int hi = hi0;

      if ( hi0 > lo0)
      {
        // Arbitrarily establishing partition element as the midpoint of
        // the array.
        Node midNode = (Node)v.elementAt( ( lo0 + hi0 ) / 2 );

        // loop through the array until indices cross
        while( lo <= hi )
        {
          // find the first element that is greater than or equal to
          // the partition element starting from the left Index.
          while( (lo < hi0) && (compare((Node)v.elementAt(lo), midNode, 0, support) < 0) )
          {
            ++lo;
          } // end while

          // find an element that is smaller than or equal to
          // the partition element starting from the right Index.
          while( (hi > lo0) && (compare((Node)v.elementAt(hi), midNode, 0, support) > 0) )
          {
            --hi;
          }

          // if the indexes have not crossed, swap
          if( lo <= hi )
          {
            swap(v, lo, hi);
            ++lo;
            --hi;
          }
        }

        // If the right index has not reached the left side of array
        // must now sort the left partition.
        if( lo0 < hi )
        {
          QuickSort2( v, lo0, hi, support );
        }

        // If the left index has not reached the right side of array
        // must now sort the right partition.
        if( lo < hi0 )
        {
          QuickSort2( v, lo, hi0, support );
        }
      }
    } // end QuickSort2  */

//  /**
//   * Simple function to swap two elements in
//   * a vector.
//   * 
//   * @param v Vector of nodes to swap
//   * @param i Index of first node to swap
//   * @param i Index of second node to swap
//   */
//  private void swap(Vector v, int i, int j)
//  {
//
//    int node = (Node) v.elementAt(i);
//
//    v.setElementAt(v.elementAt(j), i);
//    v.setElementAt(node, j);
//  }

    /**
     * This class holds the value(s) from executing the given
     * node against the sort key(s).
     *
     * @xsl.usage internal
     */
    class NodeCompareElem {

        /**
         * Current node
         */
        int m_node;

        /**
         * This maxkey value was chosen arbitrarily. We are assuming that the
         * // maxkey + 1 keys will only hit fairly rarely and therefore, we
         * // will get the node values for those keys dynamically.
         */
        int maxkey = 2;

        // Keep this in case we decide to use an array. Right now
        // using two variables is cheaper.
        //Object[] m_KeyValue = new Object[2];

        /**
         * Value from first sort key
         */
        Object m_key1Value;

        /**
         * Value from second sort key
         */
        Object m_key2Value;

        /**
         * Constructor NodeCompareElem
         *
         * @param node Current node
         * @throws javax.xml.transform.TransformerException
         */
        NodeCompareElem(int node) throws javax.xml.transform.TransformerException {
            m_node = node;

            if (!m_keys.isEmpty()) {
                NodeSortKey k1 = (NodeSortKey) m_keys.elementAt(0);
                XObject r = k1.m_selectPat.execute(m_execContext, node,
                    k1.m_namespaceContext);

                double d;

                if (k1.m_treatAsNumbers) {
                    d = r.num();

                    // Can't use NaN for compare. They are never equal. Use zero instead.
                    m_key1Value = new Double(d);
                } else {
                    m_key1Value = k1.m_col.getCollationKey(r.str());
                }

                if (r.getType() == XObject.CLASS_NODESET) {
                    // %REVIEW%
                    DTMIterator ni      = ((XNodeSet) r).iterRaw();
                    int         current = ni.getCurrentNode();
                    if (DTM.NULL == current)
                        current = ni.nextNode();

                    // if (ni instanceof ContextNodeList) // %REVIEW%
                    // tryNextKey = (DTM.NULL != current);

                    // else abdicate... should never happen, but... -sb
                }

                if (m_keys.size() > 1) {
                    NodeSortKey k2 = (NodeSortKey) m_keys.elementAt(1);

                    XObject r2 = k2.m_selectPat.execute(m_execContext, node,
                        k2.m_namespaceContext);

                    if (k2.m_treatAsNumbers) {
                        d = r2.num();
                        m_key2Value = new Double(d);
                    } else {
                        m_key2Value = k2.m_col.getCollationKey(r2.str());
                    }
                }

        /* Leave this in case we decide to use an array later
        while (kIndex <= m_keys.size() && kIndex < maxkey)
        {
          NodeSortKey k = (NodeSortKey)m_keys.elementAt(kIndex);
          XObject r = k.m_selectPat.execute(m_execContext, node, k.m_namespaceContext);
          if(k.m_treatAsNumbers)
            m_KeyValue[kIndex] = r.num();
          else
            m_KeyValue[kIndex] = r.str();
        } */
            }  // end if not empty
        }
    }  // end NodeCompareElem class
}
